1. Field of the Invention
This invention relates generally to data processing systems and, more particularly, to a system for locating and correcting errors in data using an error correction code.
2. Background Information
Data stored on magnetic media, such as magnetic disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is required to correct greater numbers of errors. The speed with which the system corrects the errors is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [for a detailed description of decoding see, Peterson and Weldon, Error Correction Codes, 2nd Ed. MIT Press, 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented xe2x80x9cGF (SP)xe2x80x9d, where xe2x80x9cSxe2x80x9d is a prime number and xe2x80x9cPxe2x80x9d can be thought of as the number of digits, base xe2x80x9cSxe2x80x9d, in each element or symbol in the field. S usually has the value 2 in digital computer and disk drive applications and, therefore, P is the number of bits in each symbol. The ECC""s commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
There are essentially four major steps in decoding a corrupted code word of a Reed-Solomon code or a BCH code. The system first determines error syndromes that are based on the results of a manipulation of the ECC symbols. Next, using the error syndromes, the system determines an error locator polynomial, which is a polynomial that has the same degree as the number of errors. The system then finds the roots of the error locator polynomial and from each root determines the location of an associated error in the code word. Finally, the system finds error values for the error locations. In binary codes, there is only one possible error value for an error location, and thus, the step of determine g error values is trivial.
The steps of determining the syndromes and finding the error locations are the most time consuming in the error correction process. The invention described herein reduces the time it takes the error correction system to find the error locations, which involves finding the roots of degree-t error locator polynomials
In many systems the roots of the error locator polynomials are determined by trial and error. The trial and error method is performed by substituting into the polynomial every possible value, i.e., every element of the applicable GF(2P) that is associated with a code word location, and for each value evaluating the polynomial. If the polynomial equals zero for a given value, the value is a root. The system continues the trial and error process by substituting a next possible value into the polynomial and determining if that value is a root; and so forth, until either all possible values have been tried or all t roots are determined. This trial and error process, which in an optimized form is commonly known as a Chien search, is time consuming. The time taken to perform the Chien search slows the error correction operations, and thus, the data processing operations of the system.
One way to speed up the Chien search is to test multiple elements simultaneously. However, as discussed with reference to FIG. 1 below, this requires including in the conventional system txe2x88x921 additional GF(2P) multipliers for each additional element tested. To test xe2x80x9cjxe2x80x9d elements simultaneously, the system requires j(txe2x88x921) GF(2p) multipliers, and the system thus readily becomes complex.
A system for performing a Chien search simultaneously tests multiple elements of GF(2P) as possible roots of a degree-t error locator polynomial "sgr"(x) using in one embodiment txe2x88x921 simplified multipliers that each simultaneously produce the corresponding terms of "sgr"(x) to test as possible roots xcex12, (xcex12)2, (xcex12)3 . . . xcex12j. Each multiplier includes a plurality of adders that are set up in accordance with precomputed terms that are based on combinations of the weight-one elements of GF(2P). A summing circuit adds together the associated terms produced by the multipliers and produces j multiple sums, which are then evaluated to test the j individual elements as possible roots. The coefficients of "sgr"(xcex12)j are then fed back to the multipliers, and the multipliers test, during a next clock cycle, the elements xcex12*(xcex12)j, (xcex12)2*(xcex12)j . . . , (xcex12)2j and so forth. The same operations are also performed for "sgr"xe2x80x2(x)="sgr"(xcex1x) to test as possible roots xcex13, xcex15, xcex17 . . . xcex12j+1.
If P=mn, that is, if P is not prime, the system may be implemented using a plurality of GF(2m) multipliers. The field GF(2m) is a subfield of GF(2P), and the elements of GF(2P) can each be represented by a combination of n elements of GF(2m). The error locator polynomial "sgr"(x) can thus be represented by a combination of n expressions "sgr"0(x), "sgr"2(x) . . . "sgr"nxe2x88x921(x), each with coefficients that are elements of GF(2m). Each of the n expressions has 2mxe2x88x921 coefficients for the terms x0, x1, x2 . . . x2mxe2x88x921. Thus, n(2mxe2x88x922) constant GF(2m) multipliers are used to test each element of GF(2P) as a possible root, as discussed in more detail below.
The number of GF(2m) multipliers in the system is independent of the degree of the error locator polynomial, and each multiplier operates over a subfield of GF(2P). Accordingly, the system can simultaneously tests j elements using j sets of n(2mxe2x88x922) multipliers over GF(2m). This is in contrast to conventional Chien search systems that require j(txe2x88x921) multipliers over GF(2P) to simultaneously test j elements.